/**
 * 时间复杂度 O(N^2)
 * 元素集合越有序，算法效率越高
 * 空间复杂度O(1)是一种稳定排序
 */
public class Sort {
    /**
     * 插入排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length ; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if (array[j]>tmp){
                     array[j+1]=array[j];
                }else {
                    //array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    public static void shellSort(int [] array){
        int gap=array.length; //n
        while (gap>1){
            gap/=2;
        shell(array,gap);

        }
    }

    /**
     * 希尔排序
     * 每组进行插入排序
     * @param array
     * @param gap
     */
    private static void shell(int[] array,int gap){
for(int i=gap;i<array.length;i++){
    int tmp=array[i];
    int j=i-gap;
    for (;j>=0;j-=gap){
        if (array[j]>tmp){
            array[j+gap]=array[i];
        }else {
            break;
        }
    }
    array[j+gap]=tmp;
}
    }


    /**
     * 两种选择排序
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int []array,int i,int j){
     int tmp=array[i];
     array[i]=array[j];
     array[j]=tmp;
}

    public static void SelectSort1(int [] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j=i+1;j< array.length;j++){
                if (array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,minIndex,i);
            
        }
    }


    public static void SelectSort(int []array){
        int left=0;
        int right= array.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex=left;

            for (int i = left+1; i < right; i++) {
        if (array[i]<array[minIndex]){
            minIndex=i;
        }
        if (array[i]>array[maxIndex]){
            maxIndex=i;
        }
      }
            swap(array,maxIndex,left);
            //如果最大值是left下标，那么上面交换完成以后
            //最大值跑到了最小值的位置，所以更新最大值下标

            if (maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }


    /**
     * 堆排序
     * @param array
     */
    private static void createBigHeap(int []array){
        for (int parent = (array.length-1-1)/2; parent>=0 ; parent--) {
            siftDown(parent,array,array.length);
        }
    }
    private static void siftDown(int parent,int[] array,int end){
       int child=2*parent+1;
       while (child<array.length) {
           if (child+1<array.length&&array[child]<array[child+1]){
               child++;
           }
           if (array[child]>parent){
               swap(array,child,parent);
               parent=child;
               child=2*parent+1;
           }else {
               break;
           }
       }
    }

    public  static void heapSort(int []array){
createBigHeap(array);
int end=array.length-1;
while (end>0){
    swap(array,0,end);
    siftDown(0,array,end);
    end--;
}
    }


}
